package com.ljx.offer;

/**
 * 两个占用内存时一样的，看有没有多占用内存，主要看用不用重新创建对象
 * @author 李捷禧
 * Date: 2023/3/23
 * ClassName: C_68
 */

public class C_68 {
    /**
     * 占用内存比哦较少
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (q.val > root.val && p.val > root.val) root = root.right;
            else if (q.val < root.val && p.val < root.val) root = root.left;
            else break;
        }
        return root;
    }

    /**
     * 这个解法占用内存比较多
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //确保q > p
        if(p.val > q.val){
            TreeNode tmp = p;
            p=q;
            q=tmp;
        }
        //q小于root证明子节点都在左边
        //同样p大于root证明子节点在root右边
        while (root != null){
            if(p.val > root.val) root = root.right;
            else if(q.val < root.val) root = root.left;
            else break;
        }
        return root;
    }
      public class TreeNode {
    int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
    }
}
